//
// Created by YeMingMing on 2024-03-13.
//
// 排序专题

#include "../esyio.h"
#include "../linklist.h"

void swap(int *a, int *b) {
    int c = *a;
    *a = *b;
    *b = c;
}

//冒泡排序
void BubbleSortV1(int nums[],int n) {
    for (int i=0;i<n-1;++i) {
        for (int j = i+1;j<n;j++) {
            if (nums[i] > nums[j]) {
                swap(&nums[i],&nums[j]);
            }
        }
    }
}
// 来自王道书
void BubbleSortV2(int nums[],int n) {
    for (int i=0;i<n-1;++i) {
        for (int j = n-1;j > i;j--) {
            if (nums[i] > nums[j]) {
                swap(&nums[i],&nums[j]);
            }
        }
    }
}

void BubbleSortV3(int nums[],int n) {
    for (int i=0;i<n;++i) {
        for (int j = 0;j < n-i-1;++j) {
            if (nums[j] > nums[j+1]) {
                swap(&nums[j],&nums[j+1]);
            }
        }
    }
}

// 快速排序
// 王道版本
int Partition(int nums[],int low,int high) {
    int pivot = nums[low];
    while (low < high) {
        while (low < high && nums[high] >= pivot) high--;
        nums[low] = nums[high];
        while (low < high && nums[low] <= pivot) low++;
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    return low;
}

// QuickSort(nums,0,n-1);
void QuickSort(int nums[],int low,int high) {
    if (low >= high) return;
    int pos = Partition(nums,low,high);
    QuickSort(nums,low,pos-1);
    QuickSort(nums,pos+1,high);
}

// 查k小
int kth_element(int nums[],int low,int high,int k) {
    int low_temp = low, high_temp = high;
    int pivot = nums[low];
    while (low < high) {
        while (low < high && nums[high] >= pivot) high--;
        nums[low] = nums[high];
        while (low < high && nums[low] <= pivot) low++;
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    if (low == k) {
        return nums[low];
    }
    else if (low > k) {
        return kth_element(nums,low_temp,low-1,k);
    }
    else {
        return kth_element(nums,low+1,high_temp,k);
    }
}

// 成电do-while实现
// 输入n和n-1都会输出最大值
int kth_element_v2(int nums[],int n,int k) {
    int low = 0, high = n-1;
    int i, j, piovt;
    do {
        i = low, j = high, piovt = nums[low];
        do {
            while (nums[j] > piovt) j--;
            while (nums[i] < piovt) i++;
            if (i < j) {
                swap(&nums[i],&nums[j]);
            }
            else {
                break;
            }
        }while (i <j);
        if (i == k) return piovt;
        else if (i > k) high = i-1;
        else low = i+1;
    }while (low < high);
    return nums[low];
}

// 链表的选择排序
void SelectSort(LinkList L) {
    LNode *p = L->next;
    while (p != NULL) {
        // 最小值默认是第一个元素
        LNode *min = p;
        // 从第二个元素开始比较
        LNode *q = p->next;
        while (q != NULL) {
            if (min->data > q->data) {
                min = q;
            }
            q = q->next;
        }
        if (min != p) {
            swap(&(p->data), &(min->data));
        }
        p = p->next;
    }
}

LinkList SelectSortV2(LinkList L) {
    LinkList head;
    InitList(&head);
    while (L->next) {
        LNode *minPrev = L; // 最小值节点的前一个节点
        LNode *min = L->next; // 最小值节点
        LNode *p = L->next; // 当前节点
        while (p->next) {
            if (p->next->data < min->data) {
                minPrev = p;
                min = p->next;
            }
            p = p->next;
        }
        // 将找到的最小值节点从原链表中移除
        minPrev->next = min->next;
        // 头插法
        min->next = head->next;
        head->next = min;
    }
    return head;
}

// 选择排序函数每次移动最小的元素到最前面
// 写不出来
void selectionSort(LinkList L) {
    LNode *p = L;
    while (p->next != NULL) {
        LNode *prev = p, *min = p->next;
        LNode *q = min;
        while (q->next != NULL) {
            if (q->next->data < min->data) {
                prev = q;
                min = q->next;
            }
            q = q->next;
        }

        //prev->next = min->next;
        p = p->next;
        PrintInt(min->data);
        // min->next = L->next;
        // L->next = min;
    }
}






// int main() {
//     LinkList L;
//     InitList(&L);
//     InsertElements(L,5,3,1,5,2,4);
//     printf("Original list:\n");
//     PrintList(L);
//     selectionSort(L);
//     printf("Sorted list:\n");
//     PrintList(L);
//     return 0;
// }




int main() {
    int n = 9;
    int nums[] = {5,6,8,4,2,3,11,9,7};
    BubbleSortV3(nums,n);
    PrintNums(nums,n);
    return 0;
}